package com.xiyun.f401t500;

import java.util.ArrayList;
import java.util.List;

/*
459. 重复的子字符串
简单
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。



示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:

输入: s = "aba"
输出: false
示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)


提示：

1 <= s.length <= 104
s 由小写英文字母组成
 */
public class RepeatSubStr_459 {

    public Object resolve() {
        String str = "aabaaba";
        return new Solution().repeatedSubstringPattern(str);
    }
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        char[] chars = s.toCharArray();
        List<Character> chList = new ArrayList<>();
        chList.add(chars[0]);
        int matchLen = 1;

        for (int i = 0; matchLen * 2 < chars.length; i += matchLen) {
            for (int j = 0; j < chList.size() && (i + j) < chars.length; j++) {
                if (chars[i + j] != chList.get(j)) {
                    i = 0;
                    chList.add(chars[matchLen++]);
                    break;
                }
            }
        }
        return true;
    }
}